package sword.offer;

/**
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class NinetyFiveII {
    /**
     * DP题 最近刷题感觉力不从心了。没有一开始的激情了，很多计划都被打乱。
     * 诶，看了下官方的解答。还是一样的老套路。
     * 二维数组动态规划
     * 第一步含义定义： dp[i][j] 表示 长度为i的str1 和 长度为j的str2 的公共子序列
     * 第二步 关系定义 或者 状态转移方程定义
     * 对于abc 和 ac 他们的最长子序列是ac
     * dp[2][2] = 1. 而 dp[3][2]=2。 我们来分析一下具体的一个转换过程
     * dp[2][2] str1[2]！= str2[2]，这个时候他们状态可能继承与 dp[1][2] 或者 dp[2][1]
     * */
    class Solution {
        public int longestCommonSubsequence(String text1, String text2) {
            int n = text1.length() + 1;
            int m = text2.length() + 1;
            int[][] dp = new int[n][m];
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < m; j++){
                    if(text1.charAt(i-1) == text1.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else{
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }
            return dp[n-1][m-1];
        }
    }
}
